/**
 * @Description: 有序数组的平方
 * 给你一个按 非递减顺序 排序的整数数组 nums，
 * 返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
 * @Date:Create in 19:34  2022/5/24
 */
public class sortedSquares0977 {

    public static void main(String[] args) {
        int[] nums = new int[]{-7, -3, 2, 3, 11};
        int[] arrs = sortedSquares2(nums);

        for (int arr : arrs) {
            System.out.println(arr);
        }
    }

    //暴力求解
    public static int[] sortedSquares1(int[] nums) {
        int[] arr = new int[nums.length];
//        int left = 0;
//        int right = nums.length-1;
        for (int i = 0; i < nums.length; i++) {
            int temp = nums[i] * nums[i];

//            arr[i] = nums[i] * nums[i];
            for (int j = i; j < nums.length; j++) {
                int temp_num = nums[i];
                if (nums[j] * nums[j] < temp) {
                    temp = nums[j] * nums[j];
                    nums[i] = nums[j];
                    nums[j] = temp_num;
//                    System.out.println(temp);
                }
            }
            arr[i] = temp;
        }

        return arr;
    }

    //双指针法
    /*我们可以使用两个指针分别指向位置 0 和 n−1，
    每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针。
    这种方法无需处理某一指针移动至边界的情况，
    */
    public static int[] sortedSquares2(int[] nums) {
        int n = nums.length;
        int[] arr = new int[n];
        for (int i = 0, j = n - 1, pos = n - 1; i <= j; ) {
            if (nums[i] * nums[i] < nums[j] * nums[j]) {
                arr[pos] = nums[j] * nums[j];
                j--;
            } else {
                arr[pos] = nums[i] * nums[i];
                i++;
            }
            pos--;
        }
        return arr;
    }



}
